## Tutorial 5 - Temporal-Difference Learning & SARSA ### Overview **Temporal-Difference (TD) learning** sits between Monte Carlo (MC) and Dynamic Programming (DP), combining an idea from each. Like MC, TD methods learn directly from raw experience generated by interacting with the environment, requiring no model of the transition dynamics $p(s', r \mid s, a)$. Like DP, TD methods **bootstrap**: they update an estimate partly on the basis of other learned estimates, without waiting for a final outcome. This combination removes MC's main restriction. Because MC only updates $V(s)$ once a full return $G_t$ is known, it must wait until an episode terminates — meaning MC cannot be applied online during episodic tasks. TD methods update after every single time step, using the very next reward and the current value estimate of the next state as a proxy for the rest of the episode. --- ### TD Prediction Recall the constant-$\alpha$ Monte Carlo update from Tutorial 4, which must wait until an episode ends to obtain the actual return $G_t$ as its update target: $$V(S_t) \gets V(S_t) + \alpha \left[ G_t - V(S_t) \right]$$ **TD(0)**, or **one-step TD**, replaces $G_t$ with a target that can be computed immediately after a single transition — the reward just received, plus the discounted current estimate of the value of the next state: $$V(S_t) \gets V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$$ The bracketed quantity is called the **TD error**: $$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$$ $\delta_t$ measures the discrepancy between $V(S_t)$'s current estimate and a better estimate formed from one real sample of what actually happened next. Notice the target $R_{t+1} + \gamma V(S_{t+1})$ is exactly the right-hand side of the Bellman equation for $v_\pi$: $$v_\pi(s) = \mathbb{E}_\pi\left[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s\right]$$ but with the *true* expectation over $p(s', r \mid s, a)$ replaced by a *single sampled* transition, and the *true* $v_\pi(S_{t+1})$ replaced by the *current estimate* $V(S_{t+1})$. This makes the target biased (it depends on a possibly-inaccurate $V(S_{t+1})$), but it has far lower variance than a full Monte Carlo return, since it depends on only one random reward and one random transition rather than the entire remaining trajectory. #### Tabular TD(0) Algorithm > **Algorithm: Tabular TD(0) for Estimating $v_\pi$** > 1. Initialize $V(s) \in \mathbb{R}$ arbitrarily for all $s \in \mathcal{S}$, except $V(\text{terminal}) = 0$. > 2. **Loop forever (for each episode):** > * Initialize $S$ > * **Loop for each step of episode:** > * $A \gets$ action given by $\pi$ for $S$ > * Take action $A$, observe $R, S'$ > * $V(S) \gets V(S) + \alpha \left[ R + \gamma V(S') - V(S) \right]$ > * $S \gets S'$ > * **until** $S$ is terminal > > *(Sutton & Barto, 2018)* Unlike the MC algorithm in Tutorial 4, there is no need to generate an entire episode trace or walk back through it — TD(0) updates $V(S)$ immediately at every step, using only quantities available at that moment. --- ### Comparing TD, MC, and DP | Feature | Dynamic Programming | Monte Carlo | Temporal-Difference | | :--- | :--- | :--- | :--- | | **Requires a model $p(s',r \mid s,a)$?** | Yes | No | No | | **Bootstraps (uses existing estimates)?** | Yes | No | Yes | | **Update timing** | Every step (full sweep) | End of episode only | Every step | | **Works on continuing (non-episodic) tasks?** | Yes | No | Yes | | **Target's bias / variance** | N/A (exact expectation) | Unbiased / high variance | Biased / low variance | Because TD targets bootstrap from single-step samples rather than full returns, TD methods are typically implemented online and incrementally, can learn from incomplete episodes, and in practice tend to converge faster than constant-$\alpha$ MC — even though, unlike MC, their targets are biased estimates of $v_\pi(s)$. --- ### From Prediction to Control As established in Tutorial 4, a model-free agent cannot construct a policy from $v_\pi(s)$ alone, since without $p(s', r \mid s, a)$ it cannot look one step ahead to see which action leads to which state. Control therefore requires estimating **action values** $q_\pi(s, a)$ directly, exactly as it did for Monte Carlo control. TD control fits into the same **Generalized Policy Iteration (GPI)** pattern used in Tutorial 4: alternate between a policy-evaluation step, which updates $Q$ towards $q_\pi$, and a policy-improvement step, which greedifies (or $\varepsilon$-greedifies) $\pi$ with respect to the updated $Q$. What changes is *how* the evaluation step is performed — one-step TD updates to $Q$ in place of full episode returns. Just as $v_\pi$ has a Bellman equation, so does $q_\pi$, and it is this equation that the TD evaluation step is sampling: $$q_\pi(s,a) = \mathbb{E}_\pi\left[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t=s,\ A_t=a\right]$$ Here the expectation over $A_{t+1}$ is taken with respect to $\pi$ — the same policy generating behavior — which is precisely what SARSA's update below approximates with a single sampled transition. This raises a question MC control did not have to address as sharply: when bootstrapping off of $Q(S', A')$, *which* action $A'$ should be used in the target? Answering this differently gives rise to two distinct families of TD control methods — **on-policy** methods, covered below as SARSA, and **off-policy** methods, covered in Tutorial 6 as Q-Learning. --- ### SARSA: On-Policy TD Control The method takes its name from the quintuple of events used in each update: $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$. This is the same TD(0) idea applied to action values rather than state values: $$Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right]$$ The crucial detail is where $A_{t+1}$ comes from: it is the action *actually selected* in state $S_{t+1}$ by the agent's current behavior policy (e.g. $\varepsilon$-greedy with respect to $Q$) — not necessarily the greedy action $\arg\max_a Q(S_{t+1}, a)$. Because the policy being evaluated (the target of the update) and the policy generating behavior (the one choosing $A_{t+1}$) are one and the same, SARSA is an **on-policy** method: it learns the value of the policy it is actually following, exploratory missteps included. #### SARSA Algorithm > **Algorithm: Sarsa (on-policy TD control) for estimating $Q \approx q_*$** > 1. Initialize $Q(s, a) \in \mathbb{R}$ arbitrarily for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$, except $Q(\text{terminal}, \cdot) = 0$. > 2. **Loop forever (for each episode):** > * Initialize $S$ > * Choose $A$ from $S$ using policy derived from $Q$ (e.g., $\varepsilon$-greedy) > * **Loop for each step of episode:** > * Take action $A$, observe $R, S'$ > * Choose $A'$ from $S'$ using policy derived from $Q$ (e.g., $\varepsilon$-greedy) > * $Q(S, A) \gets Q(S, A) + \alpha \left[ R + \gamma Q(S', A') - Q(S, A) \right]$ > * $S \gets S'$; $A \gets A'$ > * **until** $S$ is terminal > > *(Sutton & Barto, 2018)* SARSA converges to the optimal action-value function $q_*$ (with probability 1) provided all state-action pairs continue to be visited and the policy converges in the limit to the greedy policy — a condition known as **GLIE** (Greedy in the Limit with Infinite Exploration), typically achieved by decaying $\varepsilon$ toward zero over training (e.g. $\varepsilon_t = 1/t$). --- ### SARSA vs. Monte Carlo Control | Feature | Monte Carlo Control | SARSA | | :--- | :--- | :--- | | **Update frequency** | Once per episode (after termination) | Once per time step | | **Works on continuing tasks?** | No | Yes | | **Target used** | Full sampled return $G_t$ | One-step bootstrap $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ | | **Target bias / variance** | Unbiased / high variance | Biased / low variance | | **Credit assignment speed** | Slow — must wait for episode to end | Fast — propagates one step per update | The lower-variance, per-step updates of TD control generally make SARSA converge faster in practice than Monte Carlo control, and let it operate in settings — continuing tasks, or tasks with very long episodes — where waiting for a return would be impractical or impossible. SARSA is on-policy precisely because its bootstrap target uses the action the behavior policy actually chose. Tutorial 6 introduces **Q-Learning**, which instead bootstraps off of the *greedy* action regardless of what the behavior policy chose — making it an off-policy method, and setting up a direct contrast with SARSA. --- ### Quiz #### Question 1 Given $V(S_t) = 0.5$, $V(S_{t+1}) = 0.6$, observed reward $R_{t+1} = 1$, discount $\gamma = 0.9$, and step size $\alpha = 0.1$, compute the TD error $\delta_t$ and the updated value $V(S_t)$. ***Answer:*** $$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) = 1 + (0.9)(0.6) - 0.5 = 1.04$$ $$V(S_t) \gets 0.5 + (0.1)(1.04) = 0.604$$ --- #### Question 2 Why can TD(0) update $V$ online in a continuing (non-episodic) task, while Monte Carlo prediction cannot? ***Answer:*** TD(0)'s update target, $R_{t+1} + \gamma V(S_{t+1})$, only requires one reward and one next-state value estimate, both available immediately after a single transition. Monte Carlo's target is the full return $G_t$, which is only known once the episode terminates — in a continuing task, no such terminal point ever occurs, so an MC return could never actually be computed. --- #### Question 3 In the SARSA update $Q(S,A) \gets Q(S,A) + \alpha[R + \gamma Q(S',A') - Q(S,A)]$, why must $A'$ be the action actually selected by the (e.g. $\varepsilon$-greedy) behavior policy, rather than the greedy action $\arg\max_a Q(S', a)$, for SARSA to remain on-policy? ***Answer:*** On-policy methods evaluate the same policy that generates behavior. If the update instead always bootstrapped off the greedy action $\arg\max_a Q(S',a)$, the quantity being learned would be the value of the *greedy* policy, not the value of the exploratory ($\varepsilon$-greedy) policy actually controlling the agent — that would make it a different algorithm (Q-Learning, an off-policy method, covered in Tutorial 6). --- #### Question 4 An agent in state $S$ takes action $A$ with $Q(S,A) = 2.0$, receives reward $R = -1$, transitions to $S'$, and its $\varepsilon$-greedy policy selects $A'$ with $Q(S', A') = 3.0$. Using $\alpha = 0.5$ and $\gamma = 1$, what is the updated $Q(S,A)$? ***Answer:*** $$Q(S,A) \gets 2.0 + 0.5 \left[ -1 + (1)(3.0) - 2.0 \right] = 2.0 + 0.5(0) = 2.0$$ --- #### Question 5 Explain the bias/variance tradeoff between a TD(0) target and a Monte Carlo return target when estimating $v_\pi(s)$. ***Answer:*** The MC target $G_t$ is an unbiased sample of $v_\pi(s)$ (its expectation is exactly $v_\pi(s)$), but it has high variance because it depends on the full sequence of random actions, transitions, and rewards over the remainder of the episode. The TD(0) target $R_{t+1} + \gamma V(S_{t+1})$ has much lower variance, since it only depends on one random reward and one random transition, but it is biased because $V(S_{t+1})$ is itself only an estimate of $v_\pi(S_{t+1})$ rather than the true value. --- ### Sources * **Sutton, R. S., & Barto, A. G.** (2018). *Reinforcement Learning: An Introduction* (2nd ed.). MIT Press. Chapter 6: Temporal-Difference Learning. * **Morales, M.** (2020). *Grokking Deep Reinforcement Learning*. Manning Publications.